/**
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * 此题属于斐波那契数列题的变形，也可用斐波那契数列的解题方法求解
 **/

#include<iostream>
#include<vector>
using namespace std;

/**
 * Solution_1：动态规划
 * 因为一次只能跨一步or两步
 * 所以到第x级台阶的方法是到第x-1级台阶和第x-2级台阶方法之和
 **/
class Solution_1 {
public:
    int climbStairs(int n) {
        vector<int> dp(n+1);
        dp[0] = 1;
        dp[1] = 1;
        
        // dp[i+2] = dp[i+1] + dp[i]
        if(n > 1){
            for(int i=2; i<=n; i++){
                dp[i] = dp[i-1] + dp[i-2];
            }
        }
        return dp[n];
    }
};


/**
 * Solution_2：对Solution_1的空间复杂度优化
 * 同理0053，不用数组存储每步动态规划的结果，用两个整型变量实现滚动数组
 **/
class Solution {
public:
    int climbStairs(int n) {
        int result = 0;
        int d0 = 1;
        int d1 = 1;

        if(n == 1){
            result = 1;
        }
        if(n > 1){
            for(int i=2; i<=n; i++){
                result = d0 + d1;
                d0 = d1;
                d1 = result;                
            }
        }
        return result;      
    }
};

int main(){
    int x = 2;
    Solution s;
    int result = 0;
    result = s.climbStairs(x);
    cout<<result;
}